package com.linwen.excise.base;

/**
 * @author : linwen
 * @date : 下午11:29 2021/9/26
 */

import java.util.Arrays;

/**
 * 求某个区间的质数及个数
 *
 * @author lin
 * <p>
 * <p>
 * 质数也称素数指能被1和它本身整除的数
 * 2 3 5 7.。。。。
 * 1既不是质数也不是合数
 */
public class 质数 {

    public static void main(String[] args) {
        int n = 100;
        int count1 = PrimeCount1(n);
        int count2 = PrimeCount2(n);
        System.out.println(count1);
        System.out.println(count2);
    }

    public static int PrimeCount1(int n) {
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (!isPrime(i)) {
                continue;
            }
            // System.out.println(i + "\t");
            count++;
        }
        return count;
    }

    private static boolean isPrime(int x) {
        for (int i = 2; i <= x / 2; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 埃氏筛法
     * 原理：
     * 首先，将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都去掉。
     * 表中剩余最小的数字是3，3也是素数。再将表中所有3的倍数都去掉。
     * 依此类推，如果表中的剩余的最小数字是m时，m就是素数，再将其倍数都划去。
     * 最后剩余的就是素数的集合。
     * */
    public static int PrimeCount2(int n) {
        boolean[] flag = new boolean[n];// 默认是false 是素数
        int count = 0;
        for (int i = 2; i < n; i++) {
            if(!flag[i]){
                count++;
                for(int j=i;i*j<n;j++){
                    flag[j*i]=true;
                }
            }
        }
        return count;
    }
}
